package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;

/**
 * @author: xiaomi
 * @date: 2021/2/16
 * @description: 402. 移掉K位数字
 * https://leetcode-cn.com/problems/remove-k-digits/
 */
public class B_402_移掉K位数字 {

    public static void main(String[] args) {
        B_402_移掉K位数字 action = new B_402_移掉K位数字();
        test1(action);
        test2(action);
        test3(action);
        test4(action);
        test5(action);
    }

    public static void test1(B_402_移掉K位数字 action) {
        //200
        String s = "10200";
        int k = 1;
        String res = action.removeKdigits(s, k);
        System.out.println("res = " + res);
    }

    public static void test2(B_402_移掉K位数字 action) {
        //1219
        String s = "1432219";
        int k = 3;
        String res = action.removeKdigits(s, k);
        System.out.println("res = " + res);
    }

    public static void test3(B_402_移掉K位数字 action) {
        //0
        String s = "10";
        int k = 2;
        String res = action.removeKdigits(s, k);
        System.out.println("res = " + res);
    }

    public static void test4(B_402_移掉K位数字 action) {
        //0
        String s = "112";
        int k = 1;
        String res = action.removeKdigits(s, k);
        System.out.println("res = " + res);
    }

    public static void test5(B_402_移掉K位数字 action) {
        //0
        String s = "10";
        int k = 1;
        String res = action.removeKdigits(s, k);
        System.out.println("res = " + res);
    }

    /**
     * 通过模拟分析：
     * 1.删除的位置达到最大后，就不处理了。
     * 2.
     *
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits(String num, int k) {
        if (k == 0) {
            return num;
        }
        char[] chars = num.toCharArray();
        int len = chars.length;
        int size = len - k;
        if (size <= 0) {
            return "0";
        }


        ArrayDeque<Character> stack = new ArrayDeque<>(len);
        int count = 0;
        // 由于出现 0 ,所以需要新增一个关于初始 前导 0 的计数
        stack.addLast(chars[0]);
        int i = 1;
        for (; i < len; i++) {
            while (!stack.isEmpty() && stack.peekLast() > chars[i]) {
                stack.removeLast();
                count++;
                if (count == k) {
                    break;
                }
            }
            if (stack.size() < size) {
                stack.addLast(chars[i]);
            } else {
                count++;
            }

            if (count == k) {
                break;
            }

        }
        //将栈内元素进行倒序
        char[] resChars = new char[size];
        int index = stack.size();
        int endIndex = stack.size() - 1;
        while (!stack.isEmpty()) {
            resChars[endIndex--] = stack.removeLast();
        }
        for (int j = i + 1; j < len; j++) {
            resChars[index++] = chars[j];
        }
        //处理前导 0
        int beginIndex = 0;
        for (; beginIndex < size; beginIndex++) {
            if (resChars[beginIndex] != '0') {
                break;
            }
        }

        return beginIndex==size?"0":new String(resChars, beginIndex, size - beginIndex);
    }
}
